#include<vector>
using namespace std;
class Solution {
public:
    int threeSumMulti(vector<int>& A, int target) {
        int MOD = 1000000007;
        long nums[101];
        memset(nums, 0, 101 * sizeof(long));
        for (int i = 0; i < A.size(); ++i)
            ++nums[A[i]];
        long res = 0;
        for (int i = 0; i < 101; ++i) {
            if (nums[i] == 0) continue;
            for (int j = i; j < 101; ++j) {
                if (nums[j] == 0) continue;
                int k = target - i - j;
                if (k >= j && k < 101 && nums[k]>0) {
                    long tmp = 0;
                    if (i != j && i != k && j != k)
                        tmp = nums[i] * nums[j] * nums[k];
                    else if (i == j && i == k)
                        tmp = (nums[j] - 1) * (nums[k] - 2) * nums[i] / 6;
                    else {
                        int a = nums[i];
                        int b = nums[j];
                        if (nums[i] == nums[j])
                            a = nums[k];
                        else if (nums[i] == nums[k])
                            swap(a, b);
                        if (a == b) b = nums[k];
                        tmp = b * (b - 1) / 2 * a;
                    }
                    res = (res + tmp % MOD) % MOD;
                }
            }
        }
        return res;
    }
};

//int main() {
//    vector<int> A = { 16,51,36,29,84,80,46,97,84,16 };
//    Solution sol;
//    sol.threeSumMulti(A, 171);
//}